#ifndef __SKIPLIST_H__
#define __SKIPLIST_H__

#include <cstdlib>
#include <cassert>
#include <iostream>
#include <iomanip>
#include "SLNode.h"

using std::cout;
using std::endl;
using std::setw;

static const double balFactor = 0.25;
static const int maxLevel = 32;

class SkipList
{
public:
    SkipList(int k)
    {
        createList(k);
    }
    ~SkipList()
    {
        freeList();
    }

    int search(int) const;

    SLNode *insert(int);

    bool remove(int);

    void dumpAllNodes();

private:
    void createList(int);

    void freeList();

    static int getRandomLevel();

private:
    int level;
    SLNode *head, *tail;

    size_t count;
};

int SkipList::getRandomLevel()
{
    int level = 1;

    while ((random() & 0xFFFF) < (balFactor * 0xFFFF))
    {
        ++level;
    }
    return maxLevel > level ? level : maxLevel;
}

void SkipList::createList(int lastVal)
{
    tail = nullptr;
    head = new SLNode(0, maxLevel);
    for (int i = 0; i < maxLevel; ++i)
    {
        head->forwards[i].forward = tail;
        head->forwards[i].span = 0;
    }
    head->backward = nullptr;
    this->count = 0;
    this->level = 1;
}

void SkipList::freeList()
{
    SLNode *p = head, *q;
    while (p != nullptr)
    {
        q = p->forwards[0].forward;
        delete p;
        p = q;
    }
    delete p;
}

int SkipList::search(int key) const
{
    SLNode *node = head;
    int rank = 0;
    for (int i = level - 1; i >= 0; --i)
    {
        while (node->forwards[i].forward && node->forwards[i].forward->key < key)
        {
            rank += node->forwards[i].span;
            node = node->forwards[i].forward;
        }
    }

    ++rank;
    node = node->forwards[0].forward;
    if (node->key == key)
    {
        return rank;
    }
    else
    {
        return 0;
    }
    return 0;
}

SLNode *SkipList::insert(int key)
{
    SLNode *update[maxLevel], *node = head;
    int rank[maxLevel];
    for (int i = level - 1; i >= 0; --i)
    {
        rank[i] = i == (level - 1) ? 0 : rank[i + 1];
        while (node->forwards[i].forward && node->forwards[i].forward->key < key)
        {
            rank[i] += node->forwards[i].span;
            node = node->forwards[i].forward;
        }
        update[i] = node;
    }

    int nodeLevel = getRandomLevel();
    if (nodeLevel > level)
    {
        for (int i = level; i < nodeLevel; ++i)
        {
            rank[i] = 0;
            update[i] = head;
            head->forwards[i].span = count;
        }
        level = nodeLevel;
    }

    SLNode *newNode = new SLNode(key, nodeLevel);

    for (int i = 0; i < nodeLevel; ++i)
    {
        node = update[i];
        newNode->forwards[i].forward = node->forwards[i].forward;
        newNode->forwards[i].span = node->forwards[i].span - (rank[0] - rank[i]);
        node->forwards[i].forward = newNode;
        node->forwards[i].span = (rank[0] - rank[i]) + 1;
    }
    for (int i = nodeLevel; i < level; ++i)
    {
        update[i]->forwards[i].span++;
    }

    newNode->backward = (update[0] == head) ? NULL : update[0];
    if (newNode->forwards[0].forward)
    {
        newNode->forwards[0].forward->backward = newNode;
    }
    else
    {
        tail = newNode;
    }
    ++count;
    return newNode;
}

bool SkipList::remove(int key)
{
    SLNode *update[maxLevel], *node = head;
    for (int i = level - 1; i >= 0; --i)
    {
        while (node->forwards[i].forward && node->forwards[i].forward->key < key)
        {
            node = node->forwards[i].forward;
        }
        update[i] = node;
    }
    node = node->forwards[0].forward;
    if (!node || node->key != key)
    {
        return false;
    }

    for (int i = 0; i < level; ++i)
    {
        if (update[i]->forwards[i].forward != node)
        {
            update[i]->forwards[i].span--;
        }
        else
        {
            update[i]->forwards[i].forward = node->forwards[i].forward;
            update[i]->forwards[i].span += node->forwards[i].span - 1;
        }
    }
    if (node->forwards[0].forward)
    {
        node->forwards[0].forward->backward = node->backward;
    }
    else
    {
        tail = node->backward;
    }

    delete node;

    while (level > 1 && head->forwards[level - 1].forward == nullptr)
    {
        --level;
    }
    --count;

    return true;
}

void SkipList::dumpAllNodes()
{
    for (int i = level - 1; i >= 0; --i)
    {
        SLNodeLevel sn = head->forwards[i];
        /*
        while (sn.forward != nullptr)
        {
            cout << sn.span << "->";
            cout << sn.forward->key << " ";
            sn = sn.forward->forwards[i];
        }
        */
        while (sn.forward != nullptr)
        {
            cout << setw(3*sn.span) << sn.forward->key;
            sn = sn.forward->forwards[i];
        }
        cout << endl;
    }
    SLNode *p = tail;
    while (p)
    {
        cout << p->key << " ";
        p = p->backward;
    }
    cout << endl << "---------------" << endl;
}

#endif
